Packet switching devices transmit data in packets through a data network. In some protocols, data is transmitted in fixed-sized packets called cells. Each block of end-user data being transmitted is divided into cell payloads. A unique identifier, a sequence number and a destination address are attached to each cell payload to form the entire cell. The cells are independent and may traverse the data network by different routes. As a result, the transmitted cells may incur different levels of propagation delay (or latency) caused by physical paths of different lengths. The cells also may be held for varying amounts of delay time in buffers in intermediate switches in the network. Furthermore, the cells also may be switched through different numbers of packet switches as the cells traverse the network, and the switches may have unequal processing delays caused by error detection and correction.
In many packet data networks, two switching device (or switching nodes) may be coupled by more than one data link. This is done to increase bandwidth and to provide redundancy, among other reasons. As a result, a packet scheduler in a source node (or transmitting node) may transmit data packets to a destination node (or receiving node) over two or more data links. In such a multilink environment, the packet scheduler may select different links for different data packets in order to maximize throughput. The link for each data packet may be selected by any one of a number of well-known scheduling algorithms. Since the total delay on each link may be different, some data packets may arrive out of order in the destination node, thereby requiring some packet reordering at the destination. The packet reordering can significantly reduce the effective throughput (good put) of many end-user applications, particularly TCP-based applications.
However, multilink scheduling algorithms typically assume that a source node and a destination node are coupled by a plurality of homogeneous point-to-point links having equal bandwidth and equal propagation delay properties. Under this assumption, it is relatively easy to select an optimal link for sending the next data packet from the source node to the destination node without causing severe packet reordering.
However, these scheduling algorithms cannot be extended to network architectures in which packet switching devices may be coupled by a plurality of heterogeneous links having different bandwidths and different propagation delay properties. In fact, a typical bandwidth-based load-balancing algorithm used for homogenous multilinks may cause severe packet reordering, delay and jitter at the destination node when used in a network architecture using heterogeneous multilinks. The problem becomes severe when dealing with variable size packets, rather than fixed-size cells.
Therefore, there is a need in the art for improved apparatuses and methods for transmitting data packets over heterogeneous multilinks connecting nodes in a data network. In particular, there is a need for an improved packet scheduler that can select among heterogeneous multilinks in order to optimize the end-to-end delays of packet delivery and minimize the reordering or received data packets.